class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    /*
    建立一个m+1行 n+1列的dp数组
    dp[i][j]表示a[1...i]b[1..j]的最长公共子序列长度
    如果a[i]==b[j] a[i]b[j]都在公共子序列中，dp[i][j]=dp[i-1][j-1]+1
    如果a[i]!=b[j],则可以去掉a[i]或者b[j]
    dp[i][j]=max(dp[i-1][j],dp[i][j-1])，取左边或者上边的最大值
    dp数组的最右下角的值就是最长公共子序列的长度。
    同时还需要一个方向数组记录转移方向，
    */
    string LCS(string s1, string s2) {
        // write code here
        int m=s1.size();
        int n=s2.size();
        if(n==0||m==0)
            return "-1";
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
         vector<vector<int>>p(m+1,vector<int>(n+1,0));
        int i,j;
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(s1[i-1]==s2[j-1])//注意下标
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                    p[i][j]=1;//左上方
                }else if(dp[i-1][j]<dp[i][j-1]){
                    dp[i][j]=dp[i][j-1];
                    p[i][j]=2;//来自左边
                }else
                {  dp[i][j]=dp[i-1][j];
                    p[i][j]=3;//来自上边
                }
            }
        }
        int k=dp[m][n];
        string ans;
        i=m;j=n;
        while(i>0&&j>0)
        {
            if(p[i][j]==1)
            {
                //str[k--]=s1[i-1];
                ans+=s1[i-1];
                i--;j--;
            }else if(p[i][j]==2)
            {
                j--;
            }else
                i--;
        }
        reverse(ans.begin(), ans.end());
        if(ans.size()==0)
            return "-1";
        return ans;
    }   
};